package pers.tz.题目.leetcode;

import java.util.*;

/**
 * @author irony
 * @date 2024-03-17
 */
public class leetcode_0146_LRU缓存 {
// 请你设计并实现一个满足
// LRU (最近最少使用) 缓存 约束的数据结构。
//
// 实现
// LRUCache2 类：
// LRUCache2(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组
// key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
//
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
//
// 示例：
//输入
//["LRUCache2", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
//[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
//输出
//[null, null, null, 1, null, -1, null, -1, 3, 4]
//解释
//LRUCache2 lRUCache = new LRUCache2(2);
//lRUCache.put(1, 1); // 缓存是 {1=1}
//lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
//lRUCache.get(1);    // 返回 1
//lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//lRUCache.get(2);    // 返回 -1 (未找到)
//lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
//lRUCache.get(1);    // 返回 -1 (未找到)
//lRUCache.get(3);    // 返回 3
//lRUCache.get(4);    // 返回 4
//
// 提示：
// 1 <= capacity <= 3000
// 0 <= key <= 10000
// 0 <= value <= 10⁵
// 最多调用 2 * 10⁵ 次 get 和 put
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1); // 1
        lruCache.put(2, 2); // 2 1

        System.out.println(lruCache.get(1)); // 1 2  return 1

        lruCache.put(3, 3); // 3 1

        System.out.println(lruCache.get(2)); // 3 1  return -1

        lruCache.put(4, 4); // 4 3

        System.out.println(lruCache.get(1)); // 4 3  return -1
        System.out.println(lruCache.get(3)); // 3 4  return 3
        System.out.println(lruCache.get(4)); // 4 3  return 4

        // 1 -1 -1 -1 3 4
    }
}

// 最久未使用，使用是怎么定义的？是get、还是put？还是get + put都属于使用？
// 傻逼题目描述
class LRUCache {
    int capacity;
    Map<Integer, DoubleNode> table; // 数据
    DoubleList leastQueue; // 最久使用

    public LRUCache(int capacity) {
        this.table = new HashMap<>(capacity);
        this.leastQueue = new DoubleList();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (table.containsKey(key)) {
            DoubleNode node = table.get(key);
            // 移动到队尾
            leastQueue.moveToTail(node);
            return node.value;
        }

        return -1;
    }

    public void put(int key, int value) {
        if (table.containsKey(key)) {
            // update
            DoubleNode node = table.get(key);
            node.value = value;
            table.put(key, node);

            // 移动到队尾
            leastQueue.moveToTail(node);
        } else {
            // add
            DoubleNode node = new DoubleNode(key, value);
            table.put(key, node);

            // 添加到队尾
            leastQueue.add(node);

            // 新增会有超出缓存情况
            if (table.size() == capacity + 1) {
                // 移除队头
                DoubleNode head = leastQueue.removeHead();
                table.remove(head.key);
            }
        }
    }
}

class DoubleNode {
    int key;
    int value;
    DoubleNode pre;
    DoubleNode next;
    DoubleNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class DoubleList {
    DoubleNode head;
    DoubleNode tail;

    // 将node移动到队尾
    public void moveToTail(DoubleNode node) {
        if (head == tail) {
            return;
        }

        if (tail == node) {
            return;
        }

        // 将node从原来到list中剥离
        if (head == node) {
            // 特殊情况
            head = node.pre;
            head.next= null;
        } else {
            if (node.pre != null) {
                node.pre.next = node.next;
            }
            if (node.next != null) {
                node.next.pre = node.pre;
            }
        }

        // 将node添加到队尾
        tail.pre = node;
        node.pre = null;
        node.next = tail;
        tail = node;
    }

    // 添加到队尾
    public void add(DoubleNode node) {
        if (head == null && tail == null) {
            head = node;
            tail = node;
            return;
        }

        node.next = tail;
        tail.pre = node;
        tail = node;
    }

    public DoubleNode removeHead() {
        DoubleNode res = head;
        if (head == tail) {
            head = null;
            tail = null;
            return res;
        }

        // head is null 不可能出现在这个调用场景
        head = head.pre;
        head.next = null;
        return res;
    }
}

// 取巧的解法
class LRUCache2 extends LinkedHashMap<Integer, Integer> {

    private final Integer capacity;

    public LRUCache2(int capacity) {
        super(capacity, .75F, true);
        this.capacity = capacity;
    }

    public void put(int key, int value) {
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    // true if the eldest entry should be removed from the map; false if it should be retained.
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return capacity > size();
    }
}
